package f_graph_basics.a_graph_representation;

import Jama.Matrix;

import java.util.ArrayList;

/**
 * dense graph 邻接矩阵实现稠密图
 * 缺点：
 * 1.稀疏图时遍历临边效率低o（v）
 * 优点：
 * 1.自动去除平行边
 * 2.遍历邻边的顺序是按照从小到大排列 - 矩阵实现性质
 */
public class DenseGraph implements Graph{

    private int v; // vertex 顶点
    private int e; // edge 边
    private boolean isDirected; // 是否是有向图
    private boolean[][] g; // matrix graph

    /**
     * 构造函数 - 构造一个以v为顶点数的空图（没有边）
     * eg. v为4的邻接矩阵
     *      0    1   2   3  to
     * 0    0    1   0   0
     * 1    1    0   0   0
     * 2    0    0   0   1
     * 3    0    0   0   0
     * from
     * 此图表示存在4个顶点组成的图
     * 顶点id分别是0,1,2,3,4
     * 矩阵表示每个顶点与其他所有顶点也包括自身是否相连通的关系
     * 其中 0,1索引的元素互通 - 双向
     * 2通3 但是 3不通2 - 单向
     *
     *
     * @param v          顶点数
     * @param isDirected 是否是有向图
     */
    public DenseGraph(int v, boolean isDirected) {
        assert v >= 0;
        this.v = v;
        this.e = 0;
        this.isDirected = isDirected;
        this.g = new boolean[v][v];
    }

    /**
     * 图的顶点数
     * @return
     */
    public int v() {
        return this.v;
    }

    /**
     * 图的边数
     * @return
     */
    public int e() {
        return this.e;
    }

    public void addEdge(int m, int n) {
        if (hasEdge(m, n)) {
            return;
        }
        g[m][n] = true;
        if (!this.isDirected) {
            g[n][m] = true;
        }
        this.e ++;
    }

    public boolean hasEdge(int m, int n) {
        assert (m >= 0 && m < this.v) && (n >= 0 && n < this.v);
        return g[m][n];
    }

    /**
     * 通过顶点遍历邻边
     * @param vertex
     * @return
     */
    public ArrayList<Integer> getEdgesByVertex(int vertex){
        boolean[] row = this.g[vertex];
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < row.length; i++) {
            if (row[i]) {
                list.add(i);
            }
        }
        return list;
    }

    // TODO testing method to be deleted
    public void testPrint() {
        int len = this.g.length;
        double[][] d = new double[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < this.g[i].length; j++) {
                d[i][j] = this.g[i][j] ? 1 : 0;
            }
        }
        Matrix matrix = new Matrix(d);
        matrix.print(this.v, 0);
    }

    public static void main(String[] args) {
        // 无向图 = 双向图
        DenseGraph f = new DenseGraph(4, false);
        f.addEdge(0,2);
        f.addEdge(1,3);
        f.testPrint();

        System.out.println("================");
        // 有向图 = 单向图
        DenseGraph t = new DenseGraph(4, true);
        t.addEdge(0,2);
        t.addEdge(2,0);
        t.addEdge(1,0);
        t.addEdge(1,1);
        t.addEdge(1,2);
        t.addEdge(1,3);
        t.testPrint();
        ArrayList<Integer> edges = t.getEdgesByVertex(1);
        System.out.println(edges.toString());
    }
}
